Date: Wed, 08 Jan 1997 20:40:38 GMT
Server: NCSA/1.4.2
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>CSE 322: Assignment 6 Solution Set</TITLE>
</HEAD>
<BODY>
<meta name="description" value="CSE 322: Assignment 6 Solution Set">
<meta name="keywords" value="hw6soln">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>
 <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A>   <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif">   <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif">         <BR>
<B> Next:</B> <A NAME=tex2html2 HREF="node1.html">   About this document </A>
<BR> <HR> <P>
 CSE 322 Winter 1996: Assignment 6 Solution Set
<P>
<OL><LI> 
Consider the grammar (with the productions numbered 1 through 10):
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img1.gif"><P>
<P>
Here is a bottom-up parse of the string <IMG  ALIGN=MIDDLE ALT="" SRC="img2.gif">.  I've reversed the
direction of the stack so that the reductions are easier to see:
<P>
<P><IMG  ALIGN=BOTTOM ALT="" SRC="img3.gif"><P>
<P>
<LI>
Number 1, page 164.
<P>
<OL><LI> The state diagram of <b>M</b>:
<br>
<img src="hw6p2a.gif">
<P>
<LI> Computations for the following strings:
<OL><LI> <b>abaa</b>
<P>
<IMG  ALIGN=MIDDLE ALT="" SRC="img4.gif">
<P>
<LI> <b>bbbabb</b>
<P>
<IMG  ALIGN=MIDDLE ALT="" SRC="img5.gif">
<P>
<LI> <b>bababa</b>
<P>
<IMG  ALIGN=MIDDLE ALT="" SRC="img6.gif">
<P>
<LI> <b>bbbaa</b>
<P>
<IMG  ALIGN=MIDDLE ALT="" SRC="img7.gif"></OL>
<P>
<LI> Of the above strings, only <b>abaa</b>,<b>bababa</b>, and <b>bbbaa</b> are in <IMG  ALIGN=MIDDLE ALT="" SRC="img8.gif">.
<P>
<LI> One regular expression that describes <IMG  ALIGN=MIDDLE ALT="" SRC="img9.gif"> is 
<IMG  ALIGN=MIDDLE ALT="" SRC="img10.gif">.
</OL>
<P>
<LI>
Numbers 11 a) and b), page 164
<OL><LI> The state diagram for <IMG  ALIGN=MIDDLE ALT="" SRC="img11.gif">:
<br>
<img src="hw6p3a.gif">
<P>
<LI> The state diagram for <IMG  ALIGN=MIDDLE ALT="" SRC="img12.gif">:
<br>
<img src="hw6p3b.gif">
<P>
</OL></OL><BR> <HR>
<UL> 
<LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000">   About this document ... </A>
</UL>
<BR> <HR>
<P><ADDRESS>
<I>James Fix <BR>
Wed Feb 14 14:46:11 PST 1996</I>
</ADDRESS>
</BODY>
